/**
 * @Project : algorithm-learning
 * @Author : Ruoyu Wang
 * @User : Momenta
 * @DateTime : 2024/3/20 18:50
 */

//给定一个正整数n，请找出最少个数的完全平方数，使得这些完全平方数的和等于n。
//完全平方指用一个整数乘以自己例如1*1，2*2，3*3等，依此类推。
//若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。例如:1,4,9,16都是完全平方数，但是2,3,5,8,11等等不是
//数据范围: 1<= n,m <=10^4
//
//示例 1
//输入
//5
//输出
//2
//说明
//  5=1+4
//
//示例 2
//输入
//8
//输出
//2
//说明
//  8=4+4
//
//示例 3
//输入
//9
//输出
//1

#include <iostream>

using namespace std;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    int numSquares(int n) {
        int f[n + 1][n + 1];
        for (int i = 0; i <= n; ++i) {
            f[0][i] = 0x3f3f3f3f;
            f[i][0] = 0;
        }
        int res = 0x3f3f3f3f;
        for (int i = 1; i <= n / i; ++i) {
            for (int j = 1; j <= n; ++j) {
                f[i][j] = f[i - 1][j];
                if (j >= i * i) f[i][j] = min(f[i][j], f[i][j - i * i] + 1);
            }
            res = min(res, f[i][n]);
        }
        return res;
    }
};

int main() {
    Solution sl;
    printf("%d", sl.numSquares(5));
    return 0;
}